package com.fjh.algorithm.thought.sort;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author FJH
 * @date 2021/5/6 15:14
 *
 * 快速排序
 */
public class QuickSort {

    /**
     *
     * ### 1. 基本算法
     *
     * - 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
     * - 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
     */
    public void sort(int[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(int[] nums, int l, int h) {
        if (h <= l)
            return;
        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(int[] nums) {
        List<int[]> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray();
    }

    /**
     * ### 切分
     *
     * 取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，
     * 再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。
     * 不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。
     * 当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
     */
    private int partition(int[] nums, int l, int h) {
        int i = l, j = h + 1;
        int v = nums[l];
        while (true) {
            while (nums[++i] < v && i != h) ;
            while (v < nums[--j] && j != l) ;
            if (i >= j)
                break;
            Sort.swap(nums, i, j);
        }
        Sort.swap(nums, l, j);
        return j;
    }

    /**
     * ### 3. 性能分析
     *
     * 快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
     *
     * 快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。
     * 这种情况下比较次数为 C<sub>N</sub>=2C<sub>N/2</sub>+N，复杂度为 O(NlogN)。
     *
     * 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。
     * 因此最坏的情况下需要比较 N<sup>2</sup>/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
     */
}
